package com.yangzhe.algorithm.c023;

import java.io.*;

// 测试链接 : https://www.luogu.com.cn/problem/P1177
public class Code02_QuickSort_Acm {
    private static int MAX_LENGTH = 100001;
    private static int n;

    private static int[] nums = new int[MAX_LENGTH];

    public static void main(String[] args) throws IOException {
        try (InputStreamReader stream = new InputStreamReader(System.in);
             BufferedReader reader = new BufferedReader(stream);) {
            StreamTokenizer token = new StreamTokenizer(reader);
            token.nextToken();

            n = (int) token.nval;

            for (int i = 0; i < n; i++) {
                token.nextToken();
                nums[i] = (int) token.nval;
            }
        }
        quickSort(0, n - 1);
        try (OutputStreamWriter streamWriter = new OutputStreamWriter(System.out);
             PrintWriter printWriter = new PrintWriter(streamWriter);) {
            for (int i = 0; i < n; i++) {
                printWriter.print(nums[i] + " ");
            }

            printWriter.flush();
        }
    }

    public static void quickSort(int l, int r) {
        if (l >= r) {
            return;
        }

        int x = nums[l + (int) (Math.random() * (r - l + 1))];
        PartitionResult partition = partition(l, r, x);

        quickSort(l, partition.midLeft - 1);
        quickSort(partition.midRight + 1, r);

    }

    public static PartitionResult partition(int l, int r, int x) {
        PartitionResult result = new PartitionResult();
        int lBorder = l;
        int rBorder = r;
        int index = l;

        while(rBorder >= index) {
            if (nums[index] == x) {
                index++;
            } else if (nums[index] < x) {
                swap(lBorder++, index++);
            } else {
                swap(index, rBorder--);
            }
        }
        result.midLeft = lBorder;
        result.midRight = rBorder;
        return result;
    }


    protected static class PartitionResult {

        public int midLeft;
        public int midRight;
    }

    public static void swap(int x, int y) {
        // Store the value of nums[x] in a temporary variable
        int a = nums[x];
        // Set nums[x] to the value of nums[y]
        nums[x] = nums[y];
        // Set nums[y] to the value of the temporary variable
        nums[y] = a;
    }
}